1. Field of the Invention
This invention relates to the encoding and decoding of a particular class of error-correcting codes. More specifically, the invention is a novel class of codes and a method of decoding the novel class of codes utilizing an iterative algorithm.
2. Description of Related Art
There are several types of error-correcting codes that are designed to permit a decoding method that iterates to a solution approximating an optimal decoder. These types of codes are parallel-concatenated convolutional codes (also known as turbo codes), serially-concatenated convolutional codes, self-concatenated convolutional codes, and low-density parity check codes.
Parallel-concatenated convolutional codes encode a block of binary information bits by using two or more constituent convolutional encoders to create two or more vectors of parity bits corresponding to two or more subcodes. The input to each constituent encoder is a permuted version of the vector of information bits. The vectors of parity bits may possibly be punctured to increase the overall code rate. The method of iterative decoding consists of decoding each constituent subcode seperately using the so-called forward-backward BCJR algorithm (Bahl et al., “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Transactions on Information Theory, Vol. 20, pp. 284-287, March 1974) and passing the extrinsic estimates obtained for the permuted information bits among the constituent decoders for the next iteration of decoding.
Concatenated tree codes are similar to parallel-concatenated convolutional codes because the vector of information bits is used in permuted versions as the inputs to several constituent encoders. Concatenated tree codes differ from parallel-concatenated convolutional codes in that the constituent encoders may be so-called tree codes which will utilize the Belief Propagation decoding algorithm instead of the BCJR algorithm and additionally each information bit is required to be involved in the recursive-part of at least two constituent encoders.
Serially-concatenated convolutional codes encode a vector of information bits by using two constituent convolutional encoders to first create a vector of intermediate-parity bits which are appended with the information bits into a larger vector and permuted to be used as the input to a second convolutional encoder. The codeword is considered to be the information bits and the parity bits created by the second encoder (possible punctured to increase overall code rate). The method of iterative decoding consists of seperately decoding the second subcode using the so-called forward-backward BCJR algorithm to obtain extrinsic estimates for the intermediate-parity bits and the information bits, which are then passed for the decoding of the first subcode using the BCJR algorithm and the resulting extrinsic estimates are passed back for the next iteration of decoding.
Self-concatenated convolutional codes are different from serially-concatenated in that the first constituent encoder is not a convolutional encoder, but is a block encoder that simply repeats the information bits a certain number of times. All the duplicated information bits are permuted and used as the input to a convolutional encoder (possibly punctured to increase overall code rate). The iterative decoding method consists of decoding the convolutional subcode using the so-called forward-backward BCJR algorithm to obtain extrinsic estimates for all the duplications of the information bits, then the extrinsic estimates are combined and passed among duplications for the next iteration of decoding.
Low-density parity check codes are based on a binary parity check matrix with few nonzero entries. The nonzero entries on each row of the parity check matrix (for column code vectors) represent parity check functions that must be valid for a codeword. Code bits are involved in several different parity check functions. The method of iterative decoding is the so-called belief propagation algorithm which consists of computing extrinsic estimates for each parity check function, then combining estimates for duplicated code symbols and passing them to the appropriate parity check functions for the next iteration of decoding. It was shown in (Peter C. Massey, “Filling-in some of the decoding gap between Belief Propagation (BP) and Maximum A Posteriori (MAP) for convolutional codes”, Proceedings of the IEEE 2004 International Symposium on Information Theory, pp. 342, Chicago, Ill., June 27-Jul. 2, 2004) that the belief propagation decoding algorithm for low density parity check codes can be considered as the BCJR decoding of a parity check convolutional subcode based on a corresponding trellis consisting of only one state per trellis section, so each section has all branches being parallel and labeled with respect to a parity check subcode, and code symbol duplications label different trellis sections along the trellis.
Significant differences exist between the codes and methods of decoding in the prior art compared to this invention's novel codes and its method of decoding. A significant difference between parallel-concatenated convolutional codes and this invention's novel codes and its method of decoding is that a parallel-concatenated convolutional code requires decoding of two or more trellises whose symbols are not duplicated within each trellis. The same difference applies to concatenated tree code. A significant difference between self-concatenated convolutional codes and this invention's novel codes and its method of decoding is that a self-concatenated convolutional code does not linearly combine vectors of encoded parity bits componentwise over the binary field and it requires decoding a trellis that is typically much longer than the size of the information vector and the trellis does not contain duplication of parity symbols, it has duplications of the information symbols only. A significant difference between serially-concatenated convolutional codes and this invention's novel codes and its method of decoding is similar to the difference for self-concatenated convolutional codes because serially-concatenated convolutional codes do not linearly combine encoded vectors of parity bits. A significant difference between decoding a low density parity check code and this invention's novel codes and its method of decoding is that this invention utilizes a decoding trellis with more than one state per trellis section and the trellis sections are not labeled as a parity check subcode.
Related Patent Documents:
The claimed cross-reference of U.S. Provisional Patent Application No. 60/583,518 with filing date Jun. 28, 2004 contains a detailed description of this invention whereby the terminology of “Massey Codes” and its decoding method refers to the invention of this nonprovisional application.
Other References:
A document that describes a symbol-duplication trellis with more than one state per trellis-section and labeled for a convolutional subcode other than a parity check subcode was written by this inventor (Peter C. Massey, “Filling-in some of the decoding gap between Belief Propagation (BP) and Maximum A Posteriori (MAP) for convolutional codes”, Proceedings of the IEEE 2004 International Symposium on Information Theory, pp. 342, Chicago, Ill., Jun. 27-Jul. 2, 2004). The so-called forward-backward BCJR algorithm utilized within the invention's iterative decoding method was first described in the document (Bahl et al., “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Transactions on Information Theory, Vol. 20, pp. 284-287, March 1974).